perm filename OCCULT.DOC[1,BGB] blob
sn#001245 filedate 1972-11-03 generic text, type T, neo UTF8
00100 CART PROJECT JUNE 1972
00200
00300
00400 OCCULT - A HIDDEN LINE ELIMINATOR.
00500
00600 Baumgart
00700
00800
00900
01000 OCCULT may be characterized as a hidden line eliminator even
01100 though it does not directly generate line drawings but is rather a
01200 marking and editing operation on a 3D data structure. Consquently
01300 OCCULT is as much a hidden surface eliminator or a shadow caster as
01400 it is a line eliminator.
01500
01600 The general idea in OCCULT is that somehow a vertex is found
01700 to be hidden below a face or to be visible above a face; in either
01800 event the edges that form that vertex can be presumed to be likewise
01900 hidden or visible for some portion of their length starting from the
02000 known vertex. Following a hidden edge only requires checking whether
02100 that edge leaves its "over-face", whereas following a visible edge
02200 requires both checking whether the edge leaves its "under-face" as
02300 well as checking for a possible "fold crossing", this requires a
02400 "fold scan" which is where the algorithm spends most of its time. At
02500 crossings the 3D data structure is altered and two new vertices are
02600 created to form a "T-joint".
02700
02800 The reason for doing hidden line elimination in this fashion
02900 is to obtain the edge and region topology of an image for the sake of
03000 a computer vision by verification scheme. OCCULT's alleged "high
03100 speed" was not a design goal and is not really a consequence of the
03200 HIDE or SHOW edge following but rather comes from doing the hard
03300 things prior to hidden line elimination, such as finding conflicting
03400 bodies, and from the speed of the Winged Edge BFEV primitives which
03500 efficiently access and modify oriented edge structures.
00100 Prior to any hidden line eliminator, HLE, there must be a
00200 model maker. Indeed one of the nasty pitfalls in computer graphics is
00300 to invest your time, money and energy in studying or building hidden
00400 line eliminators and neglecting your model data structures and your
00500 model builders. Pretty pictures result from big complicated models, a
00600 HLE is only a translator or compiler, and little or nothing in will
00700 result in little or nothing out. The model builder that I used with
00800 OCCULT is called GEOMED [ref. x] and its data structures and two of
00900 its primitives will be briefly explained here.
01000
00100 THE MAIN CONTEXT OF OCCULT.
00200
00300 The main Context of OCCULT is held in four sets. There is
00400 POTNTF, which is the set of potential visible faces. There is POTNTE,
00500 which is the set of potential visible edges. There is FOLDE, which is
00600 the set of potential visible folded edges. There is VISINC, which is
00700 the set of visible folded edges which are incomplete, that is only
00800 one of there ends is visible.
00100 GLOSSARY
00200
00300 HLE......hidden line eliminator.
00400 POTENT.....potential visible.
00500 BFEV.......Body, Face, Edge, Vertex.
00600 UNDERFACE.........
00700 OVERFACE.........
00800 JOT.............Joint Over T.
00900 JUT.............Joint Under T.
00100 Body, Face, Edge, Vertex - Winged Data Structure.
00200
00300 GEOMED primitives - ESPLIT.
00400
00500 Terminology.
00600
00700 The visibility of each face, edge and vertex is
00800 characterized by two bits, POTENT and VISIBLE.
00900 The POTENT bit indicates that the entity is still potentially
01000 visible,
01100
01200 0 0 indicates hidden.
01300 1 0 indicates potentially visible.
01400 0 1 indicates actually visible.
01500 1 1 undefined.
01600
01700 INPUT MODEL RESTRICTIONS.
01800
01900 OCCULT is a "weak" hidden line eliminator in the sense
02000 it requires convex, coplanar, non-intersecting faces. However,
02100
02200 Concave Face Elimination.
02300 Conflicting Body Elimination.
02400
02500 Initialization.
02600 Z-clipping.
02700 Perspective Project Vertices
02800 Face Coefficients and POTENT faces.
02900 POTENT edges and Edge Coefficients.
03000 FOLDED edges.
03100
03200 A folded edge is an edge that has a single POTENT face.
03300 An edge with two POTENT faces is termed a "seam" or "crease".
00100 The main part of OCCULT consists of six subroutines:
00200
00300 VHIDE VSHOW
00400 EHIDE ESHOW
00500 MKTJ1 MKTJ2
00600
00700 The simplist of which is VHIDE(F,V) which when given that
00800 a vertex V has somehow been found to lie within and under
00900 a face F, marks that vertex as hidden and then attempts
01000 to hide all the POTENT edges of that vertex by calling EHIDE.
01100
01200 EHIDE(F,E,V) Attempts to hide as much of an edge E as
01300 is possible starting from V which is known to be hidden.
01400 There are essentially three basic cases: the edges
01500 never leaves the face covering V, the edge leaves but
01600 crosses under a seam into another occultating face
01700 or the edge crosses under a fold and EHIDE must make
01800 a T-joint by calling MKTJ1 in order to leave a portion of
01900 the edge potentially visible. EHIDE gets slightly more
02000 complicated in that the edge being hidden can rise up
02100 and strike from below one of the vertices of its covering
02200 face.
02300
02400 MKTJ1(FOLD,EDGE,V1) splits the Fold and the Edge and
02500 forms a T-Joint.